package com.ly.algorithm.leetcode.dp;

/**
 * @Classname Problem516
 * @Description
 *
 * 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
 *
 *  
 *
 * 示例 1:
 * 输入:
 *
 * "bbbab"
 * 输出:
 *
 * 4
 * 一个可能的最长回文子序列为 "bbbb"。
 *
 * 示例 2:
 * 输入:
 *
 * "cbbd"
 * 输出:
 *
 * 2
 * 一个可能的最长回文子序列为 "bb"。
 *
 *
 * @Date 2020/12/23 21:05
 * @Author 冷心影翼
 */
public class Problem516 {

	public static void main(String[] args) {
		Solution516 solution516 = new Solution516();
		System.out.println(solution516.longestPalindromeSubseq("bbbcb"));

	}

}


class Solution516 {
	public int longestPalindromeSubseq(String s) {
		int n = s.length();
		int[][] dp = new int[n][n];
		for (int i = 0; i < n; i++) {
			dp[i][i] = 1;
		}
		for (int i = n - 1; i >= 0; i--) {
			for (int j = i + 1; j < n; j++) {
				if(s.charAt(i) != s.charAt(j)) {
					dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
				}else {
					if(j-i<2)
						dp[i][j] = j-i+1;
					else
						dp[i][j] = dp[i+1][j-1]+2;
				}
			}
		}
		return dp[0][n-1];
	}
}
